108. Convert Sorted Array to Binary Search Tree

tags: Easy、Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* inorderSort(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = (left + right) / 2;
    struct TreeNode* root = createNode(nums[mid]);
    root->left = inorderSort(nums, left, mid-1);
    root->right = inorderSort(nums, mid+1, right);
    return root;
}


struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return inorderSort(nums, 0, numsSize-1);
}

解法2: 更省空間

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* inorderSort(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    int mid = (left + right) / 2;
    root->val = nums[mid];
    root->left = inorderSort(nums, left, mid-1);
    root->right = inorderSort(nums, mid+1, right);
    return root;
}


struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return inorderSort(nums, 0, numsSize-1);
}

589. N-ary Tree Preorder Traversal

tags: Easy、Tree

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

解法:

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preTrace(struct Node* node, int* array, int* index) {
    if (!node) {
        return NULL;
    }
    array[(*index)++] = node->val;
    for (int i = 0; i < node->numChildren; i++) {
        preTrace(node->children[i], array, index);
    }
    return array;
}


int* preorder(struct Node* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return 0;
    }
    int* array = (int*)malloc(10000 * sizeof(int));
    int index = 0;
    preTrace(root, array, &index);
    *returnSize = index;
    return array;
}

700. Search in a Binary Search Tree

tags: Easy、Tree

You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* findNode(struct TreeNode* node, int val) {
    if (!node) {
        return NULL;
    }
    if (node->val == val) {
        return node;
    }
    struct TreeNode* left_node = findNode(node->left, val);
    if (!left_node) {
        return findNode(node->right, val);
    }
    else {
        return left_node;
    }
}

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if (!root) {
        return NULL;
    }

    if (root->val == val) {
        return root;
    }
    return findNode(root,val);
}

解法2: 用BST的特性去搜尋

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if (!root) {
        return NULL;
    }

    struct TreeNode* curr = root;
    while (curr != NULL) {
        if (curr->val == val) {
            return curr;
        }
        else if (curr->val > val) {
            curr = curr->left;
        }
        else {
            curr = curr->right;
        }
    }
    return NULL;
}

解法3:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if (!root || root->val == val) {return root;}
    else if (root->val > val) {return searchBST(root->left, val);}
    else {return searchBST(root->right, val);}
    return NULL;
}

501. Find Mode in Binary Search Tree

tags: Easy、Tree

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void inorderTrace(struct TreeNode* node, int* array, int* index) {
    if (!node) { return;}
    inorderTrace(node->left, array, index);
    array[(*index)++] = node->val;
    inorderTrace(node->right, array, index);
}

int* findMode(struct TreeNode* root, int* returnSize) {
    int* array = (int*)malloc(10000 * sizeof(int));
    int index = 0;
    inorderTrace(root, array, &index);

    int max_count = 1;
    int curr_count = 1;
    int mode_count = 0;
    int* mode = (int*)malloc(index * sizeof(int));
    int j = 0;
    mode[mode_count++] = array[0];

    for (int i = 1; i < index; i++) {
        if (array[i] == array[i-1]) {
            curr_count++;
        }
        else {
            curr_count = 1;
        }

        if (curr_count > max_count) {
            max_count = curr_count;
            mode_count = 0;
            mode[mode_count++] = array[i];
        }
        else if (curr_count == max_count) {
            mode[mode_count++] = array[i];
        }
    }
    *returnSize = mode_count;
    return mode;
}